brute force implementation *1400

Please click on ads to support us..

Python Code:

for _ in range(int(input())):
    n, c, q = map(int, input().split())
    w = input()
    w_len = len(w)
    changes = []
    for x in range(c):
        a, b = map(int, input().split())
        w_len += b - a + 1
        changes.append([a, b, w_len])
    for y in range(q):
        query = int(input())
        if query <= n:
            print(w[query - 1])
            continue
        while query > n:
            for xx in range(len(changes)):
                if changes[xx][2] >= query:
                    query = changes[xx][1] - (changes[xx][2] - query)
                    break
            if query <= n:
                ans = query
                break
        print(w[ans - 1])

C++ Code:

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <cstdio>
#include <numeric>
typedef long long int ll;
// Geometry 


//typedef std::complex<double> point; 
//#define X real()
//#define Y imag()
//#define angle(a)                (atan2((a).imag(), (a).real()))
//#define vec(a,b)                ((b)-(a))
//#define same(p1,p2)             (dp(vec(p1,p2),vec(p1,p2)) < EPS)
//#define dp(a,b)                 ( (conj(a)*(b)).real() )	// a*b cos(T), if zero -> prep
//#define cp(a,b)                 ( (conj(a)*(b)).imag() )	// a*b sin(T), if zero -> parllel
//#define length(a)               (hypot((a).imag(), (a).real()))
//#define normalize(a)            (a)/length(a)
//#define polar(r,ang)            ((r)*exp(point(0,ang)))  ==> Already added in c++11
//#define rotateO(p,ang)          ((p)*exp(point(0,ang)))
//#define rotateA(p,ang,about)  (rotateO(vec(about,p),ang)+about)
//#define reflectO(v,m)  (conj((v)/(m))*(m))



// end of Geometry


// debuging 
#define fast ios::sync_with_stdio(false) ,  cin.tie(NULL); 
#define debug(x) cout << #x << "=" << x << endl
#define debug2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define debug3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define show(a) cout << "vector " << #a << " : " << endl ; for(auto e : a) cout << e << " " 
#define endl '\n' 
#define sz(x) (int)x.size()
// end of debuging

#endif
using namespace std;



//point reflect(point p, point p0, point p1) {
//    point z = p-p0, w = p1-p0;
//    return conj(z/w)*w + p0; // Refelect point p1 around p0p1
//}
// 
// 
//bool isCollinear(point a, point b, point c) {	
//	return fabs( cp(b-a, c-a) ) < EPS;	
//} 
// 
//bool isPointOnRay(point p0, point p1, point p2) {
//    if(length(p2-p0) < EPS) return true;
//    return same( normalize(p1-p0), normalize(p2-p0) );
//}
// 
//bool isPointOnSegment(point a, point b, point c) {
//	return isPointOnRay(a, b, c) || isPointOnRay(b, a, c);
//}
// 
// 
//double distToLine( point p0, point p1, point p2 ) {
//	return fabs(cp(p1-p0, p2-p0)/length(p0-p1)); // area = 0.5*b*h
//}
// 
//

//double distToSegment( point p0, point p1, point p2 ) {
//	double d1, d2;
//	point v1 = p1-p0, v2 = p2-p0;
//	if( (d1 = dp(v1, v2) ) <= 0)	return length(p2-p0);
//	if( (d2 = dp(v1, v1) ) <= d1)	return length(p2-p1);
//	double t = d1/d2;
//	return length(p2 - (p0 + v1*t) );
//}


//const int N=1e5+5, M=1e3+5, MOD=1e9+7,OO=0x3f3f3f3f;
//const ll LOO=0x3f3f3f3f3f3f3f3f;
//const long double EPS=1e-20;

// file input / output 
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);

struct point{
       ll l , r , real_left ,real_right ; 
      point(ll a , ll  b , ll c , ll d){
            l = a ; 
            r = b ;
            real_left = c ;
            real_right = d ;
      }
};

void taste_case(){
int n , c , q ; cin >> n >> c >> q ; 
string s ; cin >> s ;
vector<point> copys ;
copys.push_back(point(1 , n , 1 , n )) ; 
ll len =  n ; 
while(c--){
    ll real_l , real_r ; cin >> real_l >> real_r ;
    ll seg = real_r - real_l + 1 ;
    copys.push_back(point(len + 1 , len + seg  , real_l , real_r)); 
    len += seg ;
}
while(q--){
     ll x ; cin >> x ; 
      while(x  >  n ){
           for(int i = sz(copys)  - 1; i >= 0 ; --i){
                        if(x < n) break ; 
                     if(x >= copys[i].l && x <= copys[i].r){
                           ll diff = x -  copys[i].l; 
                           x  =  copys[i].real_left + diff ; 
                     }
           } 
      }
      cout << s[x-1] << endl ;
}

 
 



}



int main(){
   fast; 
   int  tt  = 1 ; 
   cin >> tt ; 
   while(tt--){
          taste_case() ; 
   }
   
   return 0 ; 
}


Comments

Submit
0 Comments
More Questions

432A - Choosing Teams
758A - Holiday Of Equality
1650C - Weight of the System of Nested Segments
1097A - Gennady and a Card Game
248A - Cupboards
1641A - Great Sequence
1537A - Arithmetic Array
1370A - Maximum GCD
149A - Business trip
34A - Reconnaissance 2
59A - Word
462B - Appleman and Card Game
1560C - Infinity Table
1605C - Dominant Character
1399A - Remove Smallest
208A - Dubstep
1581A - CQXYM Count Permutations
337A - Puzzles
495A - Digital Counter
796A - Buying A House
67A - Partial Teacher
116A - Tram
1472B - Fair Division
1281C - Cut and Paste
141A - Amusing Joke
112A - Petya and Strings
677A - Vanya and Fence
1621A - Stable Arrangement of Rooks
472A - Design Tutorial Learn from Math
1368A - C+=